//
// Created by Wesley on 25-2-7.
//
#include <vector>
#include <algorithm>
using namespace std;

#ifndef SOLUTION15_H
#define SOLUTION15_H
class Solution15 {

  public:
  // 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c 使得a + b + c = 0 ？找出所有满足条件且不重复的三元组。
  vector<vector<int>> threeSum(vector<int>& nums){
    vector<vector<int>> result;
    if (nums.size() < 3){
      return result;
    }
    // 先排序
    sort(nums.begin(), nums.end());

    for (int k = 0; k < nums.size() - 2; k++) {
      // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
      if(nums[k] > 0) {
        break;
      }

      // 当前元素和前一个元素比较 进行锚点去重
      if(k > 0 && nums[k] == nums[k-1]) {
        continue;
      }

      int left = k+1;
      int right = nums.size() -1;
      while(left < right) {
        // nums[k] + 另外两个数字
        int sum = nums[k] + nums[left] + nums[right];
        if(sum > 0) {
          --right;
        }
        else if(sum < 0) {
          left++;
        }
        else{
          result.push_back({nums[k], nums[left], nums[right]});
          // 去重
          while (left < right && nums[left] == nums[left+1]) {
            left++;
          }
          // 去重
          while (left < right && nums[right] == nums[right-1]) {
            right--;
          }
          left++;
          right--;
        }
      }
    }

    return result;
  };
};


#endif //SOLUTION15_H
